#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>

#include "common/utils.hpp"

TreeNode* parentNode;
void traversal(TreeNode* currNode, int val) {
    if (currNode == nullptr) {
        TreeNode* node = new TreeNode(val);
        if (val > parentNode->val) parentNode->right = node;
        else if (val < parentNode->val) parentNode->left = node;
        return;
    }

    parentNode = currNode;
    if (val > currNode->val) traversal(currNode->right, val);
    else if (val < currNode->val) traversal(currNode->left, val);
}

/*
在二叉搜索树中插入节点，保证插入后还是二叉搜索树即可
*/
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }

    if (val > root->val) root->right = insertIntoBST(root->right, val);
    if (val < root->val) root->left = insertIntoBST(root->left, val);

    return root;
}

extern TreeNode* commonRoot;

int main() {
    std::vector<int> nums = {4,2,7,1,3};
    TreeNode* node = createTreeNodeByArray(nums);
    printTreeNode(node);
    std::cout << "=================\n";
    TreeNode* ret = insertIntoBST(node, 5);
    printTreeNode(ret);
}